package 力扣_算法题综合.高频面试算法;

/**
 * @author zx
 * @create 2022-08-25 23:46
 */
public class 接雨水 {
    /**
     * @return 按列求(参考高赞题解：最适合自己的)
     * 时间复杂度：O(n²)    空间复杂度：O(1)
     */
    public int trap(int[] height) {
        int res = 0;
        //最两端的列不用考虑,因为一定不会有水;所以下标从1到length - 2
        for(int i = 1;i < height.length - 1;i++){
            int maxLeft = 0;
            //找出左边最高
            for(int j = i - 1;j >= 0;j--){
                if(height[j] > maxLeft){
                    maxLeft = height[j];
                }
            }
            int maxRight = 0;
            //找出右边最高
            for(int j = i + 1;j < height.length;j++){
                if(height[j] > maxRight){
                    maxRight = height[j];
                }
            }
            //找出两端最小的
            int min = Math.min(maxLeft,maxRight);
            //只有较小的一端大于当前正在处理的列才会有水,其他情况不会有水
            if(min > height[i]){
                res = res + (min - height[i]);
            }
        }
        return res;
    }

    /**
     * @return 最简写法(我一般这样干)
     */
    public int trap2(int[] height) {
        int res = 0;
        //最两端的列不用考虑,因为一定不会有水;所以下标从1到length - 2
        for(int i = 1;i < height.length - 1;i++){
            int maxLeft = 0;
            //找出左边最高
            for(int j = i - 1;j >= 0;j--){
                maxLeft = Math.max(maxLeft,height[j]);
            }
            int maxRight = 0;
            //找出右边最高
            for(int j = i + 1;j < height.length;j++){
                maxRight = Math.max(maxRight,height[j]);
            }
            //找出两端最小的
            int min = Math.min(maxLeft,maxRight);
            //只有较小的一端大于当前正在处理的列才会有水,其他情况不会有水
            if(min > height[i]){
                res = res + (min - height[i]);
            }
        }
        return res;
    }
}
